package 动态规划;

import java.util.Scanner;

/**
 * 64. 最小路径和
 *给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 * 思路：采用动态规划来解决
 * 1：定义一个二维数组dp，dp[i][j]表示到达grid[i][j]位置的最小路径和
 * 2：状态转移方程的定义：
 *      对于当前位dp[i][j]来讲，其值等于当前值+ 左侧相邻或者上一行同列的大小
 *      所以状态转移方程为：dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1])
 * 3:边界条件：
 *      第一行的格子只能从左方格子累加，即：dp[0][i] = grid[0][i] + dp[0][i-1]
 *      第一列的格子只能从上方累加，即:dp[j][0] = grid[j][0] + dp[j-1][0]
 *  4：返回最后一行的末尾，右下角即为返回值
 */
public class L_64 {
    public int minPathSum(int[][] grid) {
        // 定义状态数组
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = grid[0][0];
        // 初始化第一行元素
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        // 初始化第一列元素
        for (int j = 1; j < m; j++) {
            dp[j][0] = dp[j-1][0] + grid[j][0];
        }
        // 遍历数组,比较中间的元素
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <n ; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }

        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入行数：");
        int m = scanner.nextInt();
        System.out.println("请输入列数：");
        int n = scanner.nextInt();
        int [][] grid = new int[m][n];
        System.out.println("请输入矩阵元素：");
        for (int i = 0; i < m; i++) {
            System.out.println("请输入第" + (i + 1) + "行的元素：");
            for (int j = 0; j < n; j++) {
                System.out.println("请输入第" + (i + 1) + "行的第" + (j + 1) + "个元素：");
                grid[i][j] = scanner.nextInt();
            }
        }
        L_64 l64 = new L_64();
        int result = l64.minPathSum(grid);
        System.out.println("最小路径和为：" + result);
    }
}
